package top.minuy.structure.graph.path.dfs;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.Collections;


/**
 * 单源路径优化，深度优先遍历
 * 如若只想知道一个路径，那么可以用这个版本
 *
 * @author Minuy
 * @time 21:35
 * @date 2021/11/18
 */
public class Path {

    private Graph g;
    private int s,t;
    private boolean[] isVisited;

    private int[] pre;

    public Path(Graph g, int s,int t) {
        this.g = g;

        // 验证源顶点的合法性
        g.validateVertex(s);
        g.validateVertex(t);
        this.s = s;
        this.t = t;

        // 开辟空间，初始化内容
        this.isVisited = new boolean[g.V()];
        this.pre = new int[g.V()];
        for (int i = 0; i < this.pre.length; i++) {
            this.pre[i] = -1;
        }

        // 从源结点开始对整个联通分量进行遍历
        // （因为求路径，不同联通分量之间肯定没有路径）
        dfs(s, s);  // 深度优先遍历
    }

    /**
     * 深度优先遍历
     *
     * @param v      遍历开始的顶点
     * @param parent v的上一个被遍历的顶点
     * @author Minuy
     * @date 2021/11/16 23:42
     */
    private boolean dfs(int v, int parent) {
        isVisited[v] = true;
        pre[v] = parent;  // 记录其上一个被遍历的顶点

        if(v == t){
            // 在遍历到了目标顶点就可以返回了
            return true;
        }

        for (Integer w : g.adj(v)) {
            if (!isVisited[w]) {
               if(dfs(w, v)){
                   // 在下一个递归中遍历到了目标顶点就可以返回了
                   return true;
               }
            }
        }

        // 全部遍历了还是没找到
        return false;
    }

    /**
     * 查询源顶点是否联通到目标顶点
     *
     * @return boolean
     * @author Minuy
     * @date 2021/11/16 23:29
     */
    public boolean isConnected() {
        return isVisited[t]; // 如果被遍历到了，肯定联通
    }

    /**
     * 求到目标顶点的路径
     *
     * @return Iterable<Integer> 一个数组，可遍历，为路径上所经过的顶点
     * @author Minuy
     * @date 2021/11/16 23:32
     */
    public Iterable<Integer> path() {
        ArrayList<Integer> p = new ArrayList<>();
        if (!isConnected()) {
            // 如果不联通的，直接返回空路径列表
            return p;
        }

        int cur = t;
        while (cur != s) {
            p.add(cur);  // 记录路径
            cur = pre[cur];  // 找到它的父顶点
        }
        p.add(s); // 因为到s就出来了，所以记录一下

        // 给路径倒序一下
        Collections.reverse(p);
        return p;
    }

}
